package basic.sort.map;

/**
 * @author distantstar
 * @version 1.0
 * @date 2021
 * @description basic.sort.map
 * @since JDK1.8
 *
 * 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
 * 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
 * 此外，你可以假设该网格的四条边均被水包围。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/number-of-islands
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class NumberOfIslands {

    private static int islands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }

        // 二维数组的长度
        final int m = grid.length;
        final int n = grid[0].length;

        // 岛屿数量
        int count = 0;
        // 循环计算岛屿的数量
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 当该位置为'1'时，则将岛屿的数量加1，并且执行感染过程
                if (grid[i][j] == '1') {
                    count++;
                    inflect(grid, i, j, m, n);
                }
            }
        }

        return count;
    }

    private static void inflect(char[][] grid, int i, int j, int m, int n) {
        if (i < 0 || i == m || j < 0 || j == n || grid[i][j] != '1') {
            return;
        }

        // 将'1'变成'2'
        grid[i][j] = '2';

        // 分别从上下左右四个方向依次寻找
        inflect(grid, i - 1, j, m, n);
        inflect(grid, i + 1, j, m, n);
        inflect(grid, i, j - 1, m, n);
        inflect(grid, i, j + 1, m, n);
    }

    public static void main(String[] args) {
        char[][] grid = new char[][]{new char[]{'1', '1', '1', '1', '0'}};
        System.out.println(islands(grid));
    }
}
